TNotes.leetcode

Appearance

0040. 组合总和 II【中等】

0040. 组合总和 II【中等】 ​

1. 📝 题目描述 ​

给定一个候选人编号的集合 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1：

txt
输入：candidates =[10, 1, 2, 7, 6, 1, 5], target = 8,
输出：[
  [1, 1, 6],
  [1, 2, 5],
  [1, 7],
  [2, 6]
]

示例 2：

txt
输入：candidates =[2, 5, 2, 1, 2], target =5,
输出：[
  [1, 2, 2],
  [5]
]

提示：

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

2. 🎯 s.1 - 回溯 + 排序去重剪枝 ​

c
int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int** g_ans;
int* g_colSizes;
int g_ansSize;
int g_path[40];
int g_pathLen;

void backtrack(int* candidates, int candidatesSize, int start, int remain) {
    if (remain == 0) {
        g_ans[g_ansSize] = (int*)malloc(g_pathLen * sizeof(int));
        memcpy(g_ans[g_ansSize], g_path, g_pathLen * sizeof(int));
        g_colSizes[g_ansSize] = g_pathLen;
        g_ansSize++;
        return;
    }
    for (int i = start; i < candidatesSize; i++) {
        if (candidates[i] > remain)
            break; // 剪枝
        if (i > start && candidates[i] == candidates[i - 1])
            continue; // 跳过同层重复
        g_path[g_pathLen++] = candidates[i];
        backtrack(candidates, candidatesSize, i + 1, remain - candidates[i]);
        g_pathLen--;
    }
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume
 * caller calls free().
 */
int** combinationSum2(int* candidates, int candidatesSize, int target,
                      int* returnSize, int** returnColumnSizes) {
    qsort(candidates, candidatesSize, sizeof(int), compare);
    g_ans = (int**)malloc(2000 * sizeof(int*));
    g_colSizes = (int*)malloc(2000 * sizeof(int));
    g_ansSize = 0;
    g_pathLen = 0;
    backtrack(candidates, candidatesSize, 0, target);
    *returnSize = g_ansSize;
    *returnColumnSizes = g_colSizes;
    return g_ans;
}
js
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  candidates.sort((a, b) => a - b)
  const ans = []

  const backtrack = (start, remain, path) => {
    if (remain === 0) {
      ans.push([...path])
      return
    }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remain) break // 剪枝
      if (i > start && candidates[i] === candidates[i - 1]) continue // 跳过同层重复元素
      path.push(candidates[i])
      backtrack(i + 1, remain - candidates[i], path) // i+1：每个元素只用一次
      path.pop()
    }
  }

  backtrack(0, target, [])
  return ans
}
py
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []

        def backtrack(start: int, remain: int, path: List[int]) -> None:
            if remain == 0:
                ans.append(path[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remain:
                    break  # 剪枝
                if i > start and candidates[i] == candidates[i - 1]:
                    continue  # 跳过同层重复元素
                path.append(candidates[i])
                backtrack(i + 1, remain - candidates[i], path)  # i+1：每个元素只用一次
                path.pop()

        backtrack(0, target, [])
        return ans
  • 时间复杂度：O(2n⋅n)，其中 n 是 candidates 的长度，最多有 2n 个子集，每个结果复制需 O(n)
  • 空间复杂度：O(n)，递归栈深度最多为 n（不计输出结果）

算法思路：

  • 排序：先对 candidates 升序排序，使相同元素相邻，方便去重剪枝
  • 剪枝：candidates[i] > remain 时 break（已排序，后续更大）
  • 去重：
    • backtrack(i + 1, ...)：表示下一层从 i + 1 开始（限制每个元素只能用一次）
    • i > start && candidates[i] == candidates[i-1]：表示跳过同层枚举中的重复成员，其中 i > start 表示同层枚举，candidates[i] == candidates[i-1] 表示相同成员
  • 收集结果：当 remain == 0 时收集结果

Discussions